package com.example.skiplist17.lx;

import org.junit.jupiter.api.Test;

/**
 * 跳表的一种实现方法。
 * 跳表中存储的是正整数，并且存储的是不重复的。
 * @auther lijiewei
 * @date 2021/7/21 16:57
 */
public class SkipList {

    @Test
    public void SkipListTest() throws Exception{
        SkipList skipList = new SkipList();
        skipList.insert(1);
        skipList.insert(2);
        skipList.insert(3);
        skipList.insert(4);
        skipList.insert(5);
        skipList.insert(6);
        skipList.insert(7);
        skipList.insert(8);
        skipList.insert(9);
        skipList.printAll();
        skipList.find(9);
    }

    private static final float SKIPLIST_P = 0.5f;
    private static final int MAX_LEVEL = 16;
    private int levelCount = 1;
    //下标相同的是同一层级的索引
    private Node head = new Node();  // 带头链表


    public void insert(int value) {
        int level = randomLevel();
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;
        //不同层级索引的临时承装数组
        Node update[] = new Node[level];
        for (int i = 0; i < level; ++i) {
            update[i] = head;
        }

        //同时维护了下一层级索引的连接
        Node p = head;
        // 找到不同层级索引的插入位置
        for (int i = level - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                //查找链表的后一节点，同时会找下一层级的节点
                p = p.forwards[i];
            }
            //比新增节点大的第一个节点放入临时
            update[i] = p;
        }

        //向不同层级索引插入行节点
        for (int i = 0; i < level; ++i) {
            //（插入节点）将原本节点的续节点挂在新节点后面，新的节点插入进去
            newNode.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = newNode;
        }

        // 更新层级
        if (levelCount < level) levelCount = level;
    }

    public void printAll() {
        Node p = head;
        //第一层级的链表，依次节点打印
        while (p.forwards[0] != null) {
            System.out.print(p.forwards[0] + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }

    public Node find(int value) {
        Node p = head;
        //从最高索引层级开始循环，对比每个层级数据
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                //查找链表的后一节点，同时会找下一层级的节点
                p = p.forwards[i];
            }
        }
        //上面的循环，最后会找到最底层的链表p,因为上面判断的是小于，所以，等于value的节点在后面
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            return p.forwards[0];
        } else {
            return null;
        }
    }

    public void delete(int value) {
        //承装各层级
        Node[] update = new Node[levelCount];
        Node p = head;
        //从最高层级开始往下循环
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                //查找链表的后一节点，同时会找下一层级的节点
                p = p.forwards[i];
            }
            //将各层级第一个大于等于value的节点放入数组
            update[i] = p;
        }
        //因为上面判断的是小于，所以，等于value的节点在后面
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            //各层级去判断，值相等，就删除节点
            for (int i = levelCount - 1; i >= 0; --i) {
                if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
                    update[i].forwards[i] = update[i].forwards[i].forwards[i];
                }
            }
        }
        //非底层层级，当该层级没有后续节点时，就将层级-1（会从最高层级开始清空）
        while (levelCount>1&&head.forwards[levelCount]==null){
            levelCount--;
        }

    }


    // 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
    // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
    // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
    //        50%的概率返回 1
    //        25%的概率返回 2
    //      12.5%的概率返回 3 ...
    private int randomLevel() {
        int level = 1;

        while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
            level += 1;
        return level;
    }

    public class Node {
        private int data = -1;
        //属性承装的形式形成链表
        private Node forwards[] = new Node[MAX_LEVEL];
        private int maxLevel = 0;

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("{ data: ");
            builder.append(data);
            builder.append("; levels: ");
            builder.append(maxLevel);
            builder.append(" }");

            return builder.toString();
        }
    }
}
